МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 3 Структура даних СТЕК  Львів – 2010 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2 Постановка задачі: Реалізувати за допомогою одного масиву з N елементiв два стеки. Стеки повинні рости з кінців масиву назустріч один одному. На вході задається послідовність пар цiлих чисел (X,Y), де X - додатнє ціле число, Y - число 1 або 2. Якщо число X є парним, то воно додається в стек, якщо X є непарним числом, то зі стеку вилучається один елемент. Друге число Y кожної пари (X,Y) вказує на номер стеку, з яким виконується робота. Після обробки всієї заданої вхідної послідовності визначити в якому стеку добуток всіх парних чисел буде найменьшим. 3 Алгоритм роз’вязку задачі: Стек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку вводим кількість елементів а потім по черзі задаєм пари Х(число) та Y(номер стеку). Дані вносяться в перший чи другий стек якщо чило додатнє або видаляються якщо відємне. Після обробки всієї заданої вхідної послідовності визначаєм у якому стеку добуток парних чисел найменший. 4 Динаміка вмісту стеку: Задана послідовність: (2,1); (6,2); (12,2); (4,1); (4,2); (2,2); (6,1); (6,2); (3,1); (8,1) n дія – почерговність занесення в стек. Стек 1: Порожній стек Елементи вхідної послідовності    2 4 6 3 8     Data[4]     Data[3]     Data[2]     Data[1]  Used(   Data[0]        Data[4]     Data[3]     Data[2]   Used(   Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]        Data[4]   Used(   Data[3]   6  Data[2]   4  Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]      Функції : push(2);1 дія push(4);4 дія push(9); 7 дія pop();9 дія push(8); 10 дія   Стек 2: Порожній стек Елементи вхідної послідовності    6 12 4 2 6     Data[4]     Data[3]     Data[2]     Data[1]  Used(   Data[0]        Data[4]     Data[3]     Data[2]   Used(   Data[1]   6  Data[0]        Data[4]     Data[3]   Used(   Data[2]   12  Data[1]   6  Data[0]        Data[4]   Used(   Data[3]   4  Data[2]   12  Data[1]   6  Data[0]        Data[4]   2  Data[3]   Used( 4  Data[2]   12  Data[1]   6  Data[0]      6  Data[4]   2  Data[3]   Used( 4  Data[2]   12  Data[1]   6  Data[0]      Функції : push(6);2 дія push(12); 3 дія push(4); 5 дія push(2);6 дія push(6); 8 дія   5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась з cтруктурою даних стек. Дослідила принципи і методи роботи зі стеком. Додатки: #include <iostream> #include <conio.h> using namespace std; class Stack{ public: Stack(int N){ right=N; n=N; left=0; } void Push_left(int a){ k[left]=a; left++; } void Push_right(int a){ k[right]=a; right--; } int Top_left(){ return k[left-1]; } int Top_right(){ return k[right+1]; } void Pop_left(){ if(this->empty_left()==false) left--; } void Pop_right(){ if(this->empty_right()==false) right++; } bool empty_left(){ if(left==0) return true; else return false; } bool empty_right(){ if(right==n) return true; else return false; } bool full(){ if(left==0 && right==n) return true; else return false; } void Print_left(){ cout<<"Stack #1:\n"; if (this->empty_left()!=1){ for(int i=0;i<left;i++) cout<<k[i]<<" "; cout<<endl; } else cout<<"Stack #1 is empty!\n"; } void Print_right(){ cout...